
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* newhead = nullptr, * newtail = nullptr;
        while (head)
        {
            ListNode* next = head->next;
            if (newhead == nullptr)
                newhead = newtail = head;
            else
            {
                head->next = newhead;
                newhead = head;
            }
            head = next;
        }
        newtail->next = nullptr;
        return newhead;
    }

    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        ListNode* slow = head, * fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* rmid = reverse(slow->next);
        slow->next = nullptr;

        ListNode* newhead = head;
        while (rmid && newhead)
        {
            ListNode* rnext = rmid->next;
            ListNode* next = newhead->next;
            newhead->next = rmid;
            rmid->next = next;

            rmid = rnext;
            newhead = next;
        }
        return;
    }
};

int main()
{
    ListNode* l1 = new ListNode(1);
    ListNode* l2 = new ListNode(2);
    ListNode* l3 = new ListNode(3);
    ListNode* l4 = new ListNode(4);
    ListNode* l5 = new ListNode(5);
    l1->next = l2; l2->next = l3; l3->next = l4; l4->next = l5;
    Solution s;
    s.reorderList(l1);
    return 0;
}